package suanfa;

import java.util.*;

public class ladderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> vis=new HashSet<>();//已经搜索过的单词
        Set<String> hash=new HashSet<>();
        for(String s:wordList) hash.add(s);
        vis.add(beginWord);
        Queue<String> q=new LinkedList<>();
        if(!hash.contains(endWord)) return 0;
        q.add(beginWord);
        int ret=0;
        while(!q.isEmpty()){
            ret++;
            int ze=q.size();
            while(ze--!=0){
                String t=q.poll();
                for(int i=0;i<t.length();i++){
                    char[] tmp=t.toCharArray();
                    for(char ch='a';ch<='z';ch++){
                        tmp[i]=ch;
                        String next=new String(tmp);
                        if(!vis.contains(next) && hash.contains(next)){
                            if(next.equals(endWord)) return ret+1;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
